#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<unordered_set>
#include<algorithm>
using namespace std;

typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};


//1926.迷宫中离入口最近的出口
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance){
    //获取行数和列数
    int m = maze.size(), n = maze[0].size();
    //创建一个布尔类型的二维数组
    vector<vector<bool>> check(m, vector<bool>(n));
    //创建一个队列，存放的是数组的下标
    queue<PII> q;
    //将起始位置入队，并标记为已遍历
    q.push({entrance[0], entrance[1]});
    check[entrance[0]][entrance[1]] = true;

    int step = 0;
    while(!q.empty()){
        //每一次外层循环，表示向外扩展一层，层数就是步数，所以步数加一
        step++;
        //获取当前层有多少个下标，依次出队
        int sz = q.size();

        while(sz--){
            auto [a,b]=q.front();
            q.pop();

            //遍历当前位置的四个方向
            for (int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                if(x>=0&&x<m&&y>=0&y<n&&maze[x][y]=='.'&&check[x][y]==false){
                    //如果符合入队条件并且是出口时，直接返回当前步数
                    if(x==0||x==m-1||y==0||y==n-1){
                        return step;
                    }
                    //如果符合入队条件但不是出口时，入队并标记为已遍历
                    else{
                        q.push({x, y});
                        check[x][y] = true;
                    }
                }
            }
        }
    }

    //如果循环结束也没找到出口，说明不存在出口
    return -1;
}


//433.最小基因变化
int minMutation(string startGene, string endGene, vector<string>& bank){
    //建立两个哈希表，一个用来存放变化后的基因，防止相同的基因重复查找
    //一个用来存放基因库中的基因
    unordered_set<string> check;
    unordered_set<string> hash(bank.begin(), bank.end());

    //判断特殊情况，变化前基因等于变化后要查找的基因，直接返回0次
    if(startGene==endGene){
        return 0;
    }
    //如果变化后要查找的基因不在基因库中，直接返回-1
    if(hash.count(endGene)==0){
        return -1;
    }

    //建立一个队列,将变化前的基因入队，并存放到检查哈希表中
    queue<string> q;
    q.push(startGene);
    check.insert(startGene);

    string change = "ACGT";

    int ret = 0;
    while(!q.empty()){
        //每循环一次，相当与向外扩展一层，变化次数加一
        ret++;
        int sz = q.size();

        while(sz--){
            string t=q.front();
            q.pop();

            //i循环表示一个基因8个位置的变化，j循环表示一个位置有4种情况变化
            for (int i = 0; i < 8; i++){
                //这里内层每次循环要拷贝一下原字符串，再拷贝的基础上变化，防止原字符串变化
                string tmp = t;
                for (int j = 0; j < 4; j++){
                    tmp[i] = change[j];
                    //变化后的字符串要存在基因库中才能存放到检查哈希表中，并且不能重复存放
                    if(hash.count(tmp)!=0&&check.count(tmp)==0){
                        //如果满足上面两个条件并且就是结束字符串，直接返回当前变化次数
                        if(tmp==endGene){
                            return ret;
                        }
                        //如果不是结束字符串，入队，并且存放到检查哈希表中
                        else{
                            q.push(tmp);
                            check.insert(tmp);
                        }
                    }
                }
            }
        }
    }

    //循环结束后还没有返回，说明没有找到结束字符串，返回-1
    return -1;
}

//127.单词接龙
int ladderLength(string beginWord, string endWord, vector<string>& wordList){
    //和上一道题基因变化一样

    unordered_set<string> check;
    unordered_set<string> hash(wordList.begin(), wordList.end());

    if(beginWord==endWord){
        return 2;
    }
    if(hash.count(endWord)==0){
        return 0;
    }

    queue<string> q;
    q.push(beginWord);
    check.insert(beginWord);

    int ret = 1;
    while(!q.empty()){
        ret++;
        int sz = q.size();

        while(sz--){
            string t=q.front();
            q.pop();

            for (int i = 0; i < t.size(); i++){
                string tmp = t;
                for (char ch = 'a'; ch <= 'z'; ch++){
                    tmp[i] = ch;

                    if(hash.count(tmp)!=0&&check.count(tmp)==0){
                        if(tmp==endWord){
                            return ret;
                        }
                        else{
                            q.push(tmp);
                            check.insert(tmp);
                        }
                    }
                }
            }
        }
    }

    return 0;
}

//675.为高尔夫比赛砍树
int m = 0;
int n = 0;
int bfs(vector<vector<int>>& forest,int bx,int by,int ex,int ey){
    //如果起始位置就等于终点位置返回0
    if(bx==ex&&by==ey){
        return 0;
    }

    //初始化布尔类型的二维数组，用来标记已遍历的位置
    vector<vector<bool>> check(m, vector<bool>(n));
    //创建一个队列，将起始位置入队
    queue<PII> q;
    q.push({bx, by});
    check[bx][by] = true;

    int ret = 0;

    while(!q.empty()){
        ret++;
        int sz = q.size();

        while(sz--){
            //先获取队头元素
            auto [i, j] = q.front();
            q.pop();

            for (int k = 0; k < 4; k++){
                int x = i + dx[k], y = j + dy[k];
                if(x>=0&&x<m&&y>=0&&y<n&&forest[x][y]!=0&&check[x][y]==false){
                    if(x==ex&&y==ey){
                        return ret;
                    }
                    else{
                        q.push({x, y});
                        check[x][y] = true;
                    }
                }
            }
        }
    }

    return -1;
}
int cutOffTree(vector<vector<int>>& forest){
    //获取行数和列数
    m = forest.size();
    n = forest[0].size();
    //新建立一个数组，用来存放每个位置的下标
    vector<PII> trees;
    //遍历整个原始数组，将大于等于1的位置存放到新数组中
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(forest[i][j]>1){
                trees.push_back({i, j});
            }
        }
    }

    //按照原数组位置对应的值进行从小到大排序
    //使用Lambda表达式自定义排序规则，[&]是捕获列表，可以访问forest变量，()内是参数列表，{}内是函数体定义比较规则
    sort(trees.begin(), trees.end(), [&](const PII &p1, const PII &p2){
        return forest[p1.first][p1.second] < forest[p2.first][p2.second]; 
    });

    int bx = 0, by = 0;
    int ret = 0;
    for(auto& [a,b] : trees){
        //根据起始位置和终点位置找到最短步数
        int step = bfs(forest, bx, by, a, b);
        //如果返回的最短步数是-1，说明无法从当前起始位置到终点位置，直接输出-1
        if(step==-1){
            return -1;
        }
        //如果返回的不是-1，说明找到最短步数，累加
        ret += step;
        //将当前的终点位置作为下一个的起始位置
        bx = a, by = b;
    }

    return ret;
}

int main(){

    return 0;
}